1. Field of the Invention
The present invention relates generally to a system and method for filtering data. In particular, the present invention relates to a system and method for filtering data based on layered rule tables and data elements. Still more particularly, the present invention relates to a system and method for filtering packets based on layered rule tables and protocol elements.
2. Description of the Related Art
When data is to be processed by a computing device, a system, such as a data filtering engine, is needed to classify or filter such incoming data. For example, in a computer network, data transferred from one network device to another network device via the computer network are typically broken down into smaller blocks of data called packets. In order for a networking device to process an incoming packet, the device needs to filter or classify the incoming packet so it can determine what action should be taken on the packet. Packet filtering is a basic requirement of networking devices such as routers, upper layer switches, firewalls and bandwidth managers.
One method in the prior art is to provide a switching device with an associative memory such as a Content Addressable Memory (CAM). The initial part of the packet is then compared simultaneously with several different expected packet headers. One disadvantage of this method is that the extra bytes that must be matched in order for routing make it very expensive due to the increased width of the associative memory. Moreover, packets with variable length addresses, such as CLNP, or protocols that have variable length encapsulations, such as IPX, would require all possible combinations to be included in the associative memory thus increasing the cost of the method.
Another method in the prior art is described in U.S. Pat. No. 5,509,006 entitled “Apparatus and Method for Switching Packets Using Tree Memory” (the '006 patent) assigned to Cisco Systems. The '006 patent retrieves a data byte, compares the data byte with a protocol byte, tests the comparison result and executes a processor instruction. One disadvantage with the '006 patent is that it is difficult to implement for protocols with wide fields because it evaluates only one byte at a time. Tests of wide fields such as those used in IPv6 addresses or variable fields must be implemented as several separate tests. This requires larger memories to implement the decision tree used by the '006 patent thereby increasing the cost and decreasing the efficiency of the method.
Therefore, what is needed is a system and method for filtering data that overcomes the disadvantages of the prior art. More specifically, what is needed is a system and method for filtering data that can quickly and inexpensively test the various fields of the data. Still more particularly, what is needed is a system and method for filtering packets that can quickly and inexpensively test the various protocol fields or protocol elements of a packet regardless of the size or location of the protocol elements or the communication protocol used.